package com.ycz.algorithm.utils.spacecomlex;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author yancz
 * @ClassName SpaceComplexUtil
 * @description: 空间复杂度分析，空间复杂度衡量算法占用的内存空间随着数据量变大时的增长趋势
 * 分析空间复杂度时，通常统计暂存数据、栈帧空间、输出数据三部分
 * @date 2024-09-13 17:20:30
 * @version: 1.0
 */
public class SpaceComplexUtil {

    // 与时间复杂度不同，通常只会关注最差空间复杂度
    public static void main(String[] args) {
//        linearRecur(100);
        quadraticRecur(100);
    }

    static void algorithm(int n) {
        int a = 0; // O(1)
        int[] b = new int[10000];// O(1)
        if (n > 10) {
            int[] nums = new int[n]; // O(1)
        }
    }

    static void function() {
    }

    // 循环的空间复杂度为O(1)
    static void loop(int n) {
        for (int i = 0; i < n; i++) {
            function(); // 每次函数调用都会释放栈帧空间
        }
    }

    // 递归的空间复杂度为O(n)
    static int recur(int n) {
        if (n == 1) return 1;
        return recur(n - 1);  // 调用过程中会同时存在n个未返回的recur()，从而占用O(n)的栈帧空间
    }

    // 1. 常数阶，空间复杂度为O(1)
    // 需要注意的是，在循环中初始化变量或调用函数而占用的内存，在进入下一循环后就会被释放，因此不会累积占用空间，空间复杂度仍为O(1)
    static void constant(int n) {
        // 常量、变量、对象占用 O(1) 空间
        final int a = 0;
        int b = 0;
        int[] nums = new int[10000];
        // 循环中的变量占用 O(1) 空间
        for (int i = 0; i < n; i++) {
            int c = 0;
        }
        // 循环中的函数占用 O(1) 空间
        for (int i = 0; i < n; i++) {
            function();
        }
    }

    // 2. 线性阶，常见于元素数量与n成正比的数组、链表、栈、队列等，空间复杂度为O(n)
    static void linear(int n) {
        // 长度为n的数组占用O(n)空间
        int[] nums = new int[n];
        // 长度为 n 的列表占用 O(n) 空间
        List<Node> nodes = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            nodes.add(new Node(4));
        }
        // 长度为 n 的哈希表占用 O(n) 空间
        Map<Integer, String> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(i, String.valueOf(i));
        }
    }

    // 线性阶(递归实现)
    // 函数的递归深度为n，即同时存在n个未返回的linearRecur函数，使用O(n)大小的栈帧空间
    static void linearRecur(int n) {
        System.out.println("递归n = " + n);
        if (n == 1) return;
        linearRecur(n - 1);
    }

    // 3. 平方阶，常见于矩阵和图，元素数量与n成平方关系，空间复杂度为O(n^2)
    static void quadratic(int n) {
        // 矩阵占用 O(n^2) 空间
        int[][] numMaxtrix = new int[n][n];
        // 二维列表占用 O(n^2) 空间
        List<List<Integer>> numList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            List<Integer> tmp = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                tmp.add(0);
            }
            numList.add(tmp);
        }
    }

    // 平方阶（递归实现）
    static int quadraticRecur(int n) {
        if (n <= 0) return 0;
        int[] nums = new int[n];
        System.out.println("递归 n = " + n + "中的nums长度=" + nums.length);
        return quadraticRecur(n - 1);
    }

    // 4. 指数阶，常见于二叉树中，空间复杂度为O(2^n)
    static TreeNode buildTree(int n) {
        if(n == 0) return null;
        TreeNode root = new TreeNode(0);
        root.left = buildTree(n - 1);
        root.right = buildTree(n - 1);
        return root;
    }

    // 5. 对数阶，常见于分治算法中，比如归并排序


}
